////2009/07/25 14:19:12
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

class MergeSort
{
public:
    int howManyComparisons(vector <int> numbers)
    {
        return mergeSort(numbers);
    }
private:
	int mergeSort(vector<int>& a)
	{
		if (a.size() <= 1)
            return 0;
		int k = a.size() / 2;
		vector<int> b = vector<int> (a.begin(), a.begin() + k);
		vector<int> c = vector<int> (a.begin() + k, a.end());
		return mergeSort(b) + mergeSort(c) + merge(a, b, c);
	}
	int merge(vector<int>& a, vector<int>& b, vector<int>& c)
	{
		int score = 0;
		int index = 0;		// For a;
		int i = 0;			// FOr b;
		int j = 0;			// For c;
		for(; i<b.size()&& j<c.size();)
		{
			if(b[i] == c[j])
			{
				a[index++] = b[i++];
				a[index++] = c[j++];
				score ++;
			}
			else if(b[i] > c[j])
			{
				a[index++] = c[j++];
				score++;
			}
			else
			{
				a[index++] = b[i++];
				score++;
			}
		}
		for(;i<b.size();)
		{
			a[index++] = b[i++];
		}
		for(;j<c.size();)
		{
			a[index++] = c[j++];
		}
		return score;
	}
};
/*
 * List mergeSort(List a)
 * 1. if size(a) <= 1, return a
 * 2. split a into two sublists b and c
 * 	  if size(a) = 2*k, b contains the first k elements of a, c the last k elements
 *    if size(a) = 2*k+1, b contains the first k elements of a, c the last k+1 elements
 * 3. List sb = mergeSort(b)
 *    List sc = mergeSort(c)
 * 4. return merge(sb, sc)
 * 
 * List merge(List b, List c)
 * 1. create an empty list a
 * 2. while both b and c are not empty, compare the first elements of b and c
 *    first(b) < first(c): remove the first element of b and append it to the end of a
 *    first(b) > first(c): remove the first element of c and append it to the end of a
 *    first(b) = first(c): remove the first elements of b and c and append them to the end of a
 * 3. if either b or c is not empty, append that non-empty list to the end of a
 * 4. return a
 * 
 * http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm151
 * */
